N-th tribonacci number [Fibonacci Number]

Time: O(LogN); Space: O(1); easy

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and

Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4

Output: 4

Explanation:

  • T_3 = 0 + 1 + 1 = 2

  • T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25

Output: 1389537

Constraints:

  • 0 <= n <= 37

  • The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Hints:

  1. Make an array F of length 38, and set F[0] = 0, F[1] = F[2] = 1.

  2. Now write a loop where you set F[n+3] = F[n] + F[n+1] + F[n+2], and return F[n].

1. Dynamic programming [O(LogN), O(1)]

[5]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def tribonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        def matrix_mult(m1, m2):
            return [[sum(a * b for a, b in zip(m1_row, m2_col)) for m2_col in zip(*m2)] for m1_row in m1]

        def identity(size):
            size = range(size)
            return [[(i == j) * 1 for i in size] for j in size]

        def matrix_exp(m, pow):
            assert pow >= 0 and int(pow) == pow, "Only non-negative, integer powers allowed"
            accumulator = identity(len(m))
            for i in range(pow):
                accumulator = matrix_mult(accumulator, m)
            return accumulator

        def print_table(data):
            for row in data:
                print(' '.join('%-5s' % ('%s' % cell) for cell in row))

        T = [[1, 1, 0],
             [1, 0, 1],
             [1, 0, 0]]

        m_exp = matrix_exp(T, n)
        res = matrix_mult([[1, 0, 0]], m_exp)

        return res[0][1]

[6]:

s = Solution1()
n = 4
assert s.tribonacci(n) == 4
n = 25
assert s.tribonacci(n) == 1389537

2. Simplest

[7]:

class Solution2(object):
    def tribonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        a, b, c = 0, 1, 1
        for _ in range(n):
            a, b, c = b, c, a+b+c
        return a

[8]:

s = Solution2()
n = 4
assert s.tribonacci(n) == 4
n = 25
assert s.tribonacci(n) == 1389537